This invention relates to linear interpolators. More particularly, this invention relates to linear interpolators that are accurate and cost-effectively implemented in hardware.
Linear interpolation may be the simplest, fastest, and most commonly implemented form of interpolation. It is based on a straight line relationship between two values, points, pixels, colors, etc. Linear interpolation is a well-known mathematical operation that computes a value between two known values given the ratios of a distance from each known value to an intermediate value divided by the distance between the two known values. For example, given two values P1 and P2, and given that the ratio of a distance from an intermediate value to P2 divided by the distance between P1 and P2 is R1, and the ratio of a distance from the intermediate value to P1 divided by the distance between P1 and P2 is R2, the interpolated value IV1, can be represented as follows:
IV1=R1*P1+R2*P2xe2x80x83xe2x80x83(1) 
The sum of the two ratios, R1 and R2, is equal to one. Therefore, the interpolated value can be represented in terms of one ratio. Assigning R1 to F, commonly known as the linear interpolation factor, IV1 can be represented as follows:
Iv2=F*P1+(1xe2x88x92F)*P2xe2x80x83xe2x80x83(2) 
This is a preferred equation for representing linear interpolation because the two distance ratios are in terms of one ratio, F.
Implementing this interpolation in, for example, Application Specific Integrated Circuit (AISC) hardware typically requires two multipliers, an adder, and a subtractor. Primarily because of the multipliers, this conventional approach is expensive to implement. Multipliers occupy large amounts of circuit area because of the number and sizes of transistors included in each. Because adders require less transistors and thus occupy less circuit area, adders are less expensive to implement. As a result, adders are preferred over multipliers where cost is an issue.
A second approach to linear interpolation reduces the cost somewhat by approximating one of the distance ratios. Because (1xe2x88x92F) is approximately equal to xcx9cF, which is the logically inverted value of F, or the one""s complement of F, the interpolated value IV2 can be represented as follows:
Iv2=F*P1+xcx9cF*P2xe2x80x83xe2x80x83(3) 
This approach typically requires two multipliers, an adder, and an inverter. Although the use of an inverter rather than a subtractor as in the conventional approach reduces the hardware implementation cost somewhat, an error is introduced because of the approximation.
A third approach uses the approximation described in the second approach to construct a set of multi-bit values M. Assuming P1, P2, and M have the same number of bits and that F has n bits, the multi-bit values M can be determined as follows:                                                         M              0                                            =                                              F              ⁢                              xe2x80x83                            [              0              ]                                            ?                                P1                                :                                P2                                                              M              1                                            =                                              F              ⁢                              xe2x80x83                            [              1              ]                                            ?                                P1                                :                                P2                                                              M              2                                            =                                              F              ⁢                              xe2x80x83                            [              2              ]                                            ?                                P1                                :                                P2                                                              xe2x80x83                                                          xe2x80x83                                                          xe2x80x83                                            ⋮                                              xe2x80x83                                                          xe2x80x83                                                          xe2x80x83                                                                          M                              n                -                1                                                          =                                              F              ⁢                              xe2x80x83                            [                              n                -                1                            ]                                            ?                                P1                                :                                P2                                              (        4        )            
The multi-bit values M in equation (4) can be represented using xe2x80x9cCxe2x80x9d programming language notation (other suitable notations can also be used). The question mark represents a select function dependent on a specified bit of F. For example, if the specified bit of F is equal to binary xe2x80x9c1xe2x80x9d M is assigned the value immediately after the question mark (P1). If the specified bit of F is equal to binary xe2x80x9c0xe2x80x9d, M is assigned the value immediately after the colon (P2). Using the multi-bit values, IV2 can be represented as follows:
IV2=[M0+(M1 less than  less than 1)+(M2 less than  less than 2)+ . . . +(Mnxe2x88x921 less than  less than (nxe2x88x921))] greater than  greater than nxe2x80x83xe2x80x83(5) 
The operator xe2x80x9c less than  less than xe2x80x9d means a logical shift left (shifting a zero in the least significant bit position). The operator xe2x80x9c greater than  greater than xe2x80x9d means a logical shift right (shifting out the least significant bit position). The number of bits to shift left or right is indicated by a number immediately to the right of the operator xe2x80x9c less than  less than xe2x80x9d or xe2x80x9c greater than  greater than .xe2x80x9d Shifting aligns the multi-bit values in the correct bit position prior to adding (e.g., if M and F are 4 bits, M0=0000.xxxxb, M1 less than  less than =000x.xxx0b, M2 less than  less than 2=00xx.xx00b, and M3 less than  less than 3=0xxx.x000b). Shifting the sum of these multi-bit values by n removes the fractional part of the interpolated result. Prior to shifting right by n, the summation produces a term in the form xe2x80x9cxxxx.xxxxb.xe2x80x9d After the shift, IV2 can be represented in the form xe2x80x9cxxxxb.xe2x80x9d
This approach significantly reduces the cost of implementing an interpolator to perform this calculation by eliminating the use of multipliers. The multi-bit values allow the interpolation to be implemented using only (nxe2x88x921) adders and shifters, which occupy less area in hardware and are thus less expensive to implement than the multipliers used in the conventional approach. However, as with the second approach, approximating (1xe2x88x92F) with xcx9cF introduces an error. Therefore, the interpolated value does not have the same accuracy as that of the conventional approach.
In view of the foregoing, it would be desirable to provide a linear interpolator that is both accurate and cost effective to implement in hardware.
It is an object of this invention to provide a linear interpolator that is both accurate and cost effective to implement in hardware.
In accordance with this invention, a linear interpolator is provided that combines the accuracy of the conventional approach with the cost effective implementations of other known approaches. The present invention uses multi-bit values to eliminate the use of multipliers. Moreover, the present invention improves interpolation accuracy by representing the distance ratios more accurately as follows: because F is a fraction between zero and one inclusive (i.e., 0xe2x89xa6Fxe2x89xa61), xe2x88x92F is equivalent to xcx9cF+1(lsb) (i.e., a binary xe2x80x9c1xe2x80x9d in the least significant bit position), or the two""s complement of F. Through algebraic manipulations, linear interpolation can be accurately performed using the multi-bit value approach in equation (5) when the following two terms are preferably added to the multi-bit value summation prior to shifting right by n: (P2 less than  less than n) and P2. These two terms correct the inherent error common in known linear interpolators.
The present invention requires (n+1) adders, which are less costly to implement than approaches involving multipliers. The (n+1) adders represent only a modest increase in the number of devices as compared to known approaches, but result in substantially the same accuracy as the conventional approach while requiring less circuit area to implement.
Advantageously, linear interpolators of the present invention can be combined. For example, three linear interpolators can be combined to form a bilinear interpolator that operates on four values and two distance ratios. Similarly, seven linear interpolators of the present invention can be combined to form a trilinear interpolator that operates on eight values and three distance ratios.
Linear interpolators of the present invention can be advantageously used, for example, in texture filter circuits associated with computer graphics.